package _00_sameTree

import "fmt"

/*
Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

求解这道题需要使用分治法

Input:     p         p`
          / \       / \
         pl  pr    pl`  pr`
		/ \
	   ... 		   ...
我们站在p和p`上来看问题，如果两棵树相等，那么
1. p==p`
2. p的左子树等于p`的左子树
3. p的右子树等于p`的右子树

考虑上边界值null
当p==null&&p`==null时，两树相等
当p或p`中只有一个为Null时，不相等
当p和p`都不为null且两节点相等时，只要p和p`的左子树以及p和p`的右子树都相等即可
![20180809153375266745293.png](http://cdn.bsummer.cn/20180809153375266745293.png)
*/

func main() {
	fmt.Println(isSameTree(generateP(), generateQ()))
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p == nil || q == nil {
		return false
	} else {
		return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	}
}

func generateP() *TreeNode {
	pl := TreeNode{
		Val:   1,
		Left:  nil,
		Right: nil,
	}

	pr := TreeNode{
		Val:   2,
		Left:  nil,
		Right: nil,
	}

	p := TreeNode{
		Val:   3,
		Left:  &pl,
		Right: &pr,
	}

	return &p
}

func generateQ() *TreeNode {
	ql := TreeNode{
		Val:   1,
		Left:  nil,
		Right: nil,
	}

	qr := TreeNode{
		Val:   2,
		Left:  nil,
		Right: nil,
	}

	q := TreeNode{
		Val:   3,
		Left:  &ql,
		Right: &qr,
	}

	return &q
}

func isSameTree(p, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p == nil || q == nil {
		return false
	} else {
		return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	}
}
